package leetcode.code0028;

public class Solution {
	public int strStr(String haystack, String needle) {
		char[] need = needle.toCharArray();
		int len = needle.length();
		int[] next = new int[len];
		for (int r = 1, l = 0; r < len; r++) {
			while (l > 0 && need[l] != need[r]) {
				l = next[l - 1];
			}
			if (need[l] == need[r]) {
				l++;
			}
			next[r] = l;
		}

		char[] h = haystack.toCharArray();
		for (int r = 0, l = 0; r < haystack.length(); r++) {
			while (l > 0 && need[l] != h[r]) {
				l = next[l - 1];
			}
			if (need[l] == h[r]) {
				l++;
			}
			if (l == len) {
				return r - len + 1;
			}
		}
		return -1;
	}
}
